Multicomponent problems are hard to solve as each component has the potential to influence the feasibility as well as the quality of the other components [4]. Among the studied multi-component problems, vehicle routing problems with loading constraints [15] appear to be very frequently investigated. In these problems, tour are to be created for vehicles while constraints and aims of specific loading policies must be taken into account. One of these problems is the Traveling Thief Problem (TTP), which combines two classic well-known and well-studied problems: the Knapsack Problem (KP) and the Traveling Salesman Problem (TSP). The TTP was proposed in 2013 by Bonyadi et al. [3] in order to provide an academic abstraction of multi-component problems for the scientific community. In the TTP, a thief travels across all cities (TSP component) and steals items along the way (KP component).

The Thief Orienteering Problem (ThOP) is a multi-component problem that combines features of two classic combinatorial optimization problems: Orienteering Problem and Knapsack Problem. The ThOP is challenging due to the given time constraint and the interaction between its components. We propose an Ant Colony Optimization algorithm together with a new packing heuristic to deal individually and interactively with problem components. Our approach outperforms existing work on more than 90% of the benchmarking instances, with an average improvement of over 300%.

The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components: the travelling salesman problem (TSP) and the knapsack problem (KP). Recent state-of-the-art TTP solvers modify the underlying TSP and KP solutions in an iterative and interleaved fashion. The TSP solution (cyclic tour) is typically changed in a deterministic way, while changes to the KP solution typically involve a random search, effectively resulting in a quasi-meandering exploration of the TTP solution space. Once a plateau is reached, the iterative search of the TTP solution space is restarted by using a new initial TSP tour. We propose to make the search more efficient through an adaptive surrogate model (based on a customised form of Support Vector Regression) that learns the characteristics of initial TSP tours that lead to good TTP solutions. The model is used to filter out non-promising initial TSP tours, in effect reducing the amount of time spent to find a good TTP solution. Experiments on a broad range of benchmark TTP instances indicate that the proposed approach filters out a considerable number of non-promising initial tours, at the cost of omitting only a small number of the best TTP solutions.

In the travelling thief problem (TTP), a thief undertakes a cyclic tour through a set of cities, and according to a picking plan, picks a subset of available items into a rented knapsack with limited capacity. The overall aim is to maximise profit while minimising renting cost. TTP combines two interdependent components: the travelling salesman problem (TSP) and the knapsack problem (KP). Existing TTP approaches typically solve the TSP and KP components in an interleaved fashion: the solution of one component is fixed while the solution of the other is changed. This indicates poor coordination between solving the two components, which may lead to poor quality TTP solutions. The 2-OPT heuristic is often used for solving the TSP component, which reverses a segment in the tour. Within the TTP context, 2-OPT does not take into account the picking plan, which can result in a lower objective value. This in turn can result in the tour modification to be rejected by a solver. To address this, we propose an extended form of 2-OPT in order to change the picking plan in coordination with modifying the tour. Items deemed as less profitable and picked in cities earlier in the reversed segment are replaced by items that tend to be equally or more profitable and not picked in cities later in the reversed segment. The picking plan is further changed through a modified form of the bit-flip search, where changes in the picking state are only permitted for boundary items, which are defined as lowest profitable picked items or highest profitable unpicked items. This restriction reduces the amount of time spent on the KP component, allowing more tours to be evaluated by the TSP component within a given time budget. The two modified heuristics form the basis of a new cooperative coordination solver, which is shown to outperform several state-of-the-art TTP solvers on a broad range of benchmark TTP instances.

The travelling thief problem (TTP) is a combination of two interdependent NP-hard components: travelling salesman problem (TSP) and knapsack problem (KP). Existing approaches for TTP typically solve the TSP and KP components in an interleaved fashion, where the solution to one component is held fixed while the other component is changed. This indicates poor coordination between solving the two components and may lead to poor quality TTP solutions. For solving the TSP component, the 2-OPT segment reversing heuristic is often used for modifying the tour. We propose an extended and modified form of the reversing heuristic in order to concurrently consider both the TSP and KP components. Items deemed as less profitable and picked in cities earlier in the reversed segment are replaced by items that tend to be equally or more profitable and not picked in the later cities. Comparative evaluations on a broad range of benchmark TTP instances indicate that the proposed approach outperforms existing state-of-the-art TTP solvers.